package com.zhugang.week09;

/**
 * @program algorithms
 * @description: wordExit
 * @author: chanzhugang
 * @create: 2022/08/23 17:03
 */
public class WordExist {

    /**
     * 79 单词搜索
     * 图上的匹配问题， 用回溯理解
     *
     * @param board
     * @param word
     * @return
     */
    private boolean existed = false;
    private int h;
    private int w;

    public boolean exist(char[][] board, String word) {
        // 二维网格里找word是否存在， 相邻单元格：水平垂直
        h = board.length;
        w = board[0].length;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                // 每次重新申请
                boolean[][] visited = new boolean[h][w];
                // 以i、j为顶点
                dfs(board, word, i, j, 0, visited);
                if (existed) return true;
            }
        }
        return false;
    }

    private void dfs(char[][] board, String word, int i, int j, int k, boolean[][] visited) {
        if (existed) {
            return;
        }
        if (word.charAt(k) != board[i][j]) {
            return;
        }
        visited[i][j] = true;
        if (k == word.length() - 1) {
            // 单词的每个字符都存在
            existed = true;
            return;
        }

        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int di = 0; di < 4; di++) {
            int newi = i + dirs[di][0];
            int newj = j + dirs[di][1];
            if (newi >= 0 && newi < h && newj >= 0 && newj < w && visited[newi][newj] == false) {
                // 边界条件 和 没访问过
                dfs(board, word, newi, newj, k + 1, visited);
            }
        }
        // 没用的路径需要重置（）
        visited[i][j] = false;
    }
}